<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8" />
  <meta name="viewport" content="width=device-width, initial-scale=1.0" />
  <title>Document</title>
</head>

<body>

  <script>
    // 空间复杂度O(log n) 最差O(n)是递归调用栈的深度 原地排序辅助空间为O(1)
    // function quickSort(arr) {
    //   if (arr.length <= 1) return arr;
    //   let pivot = arr.shift(); //基准数(每次都要删除数组的第一个元素，将它作为基准数)
    //   let left = [],
    //     right = [];



    //   for (let i = 0; i < arr.length; i++) {
    //     if (arr[i] < pivot) left.push(arr[i]);
    //     else right.push(arr[i]);
    //   }
    //   return [...quickSort(left), pivot, ...quickSort(right)];
    // }

    // 原地修改
    function quickSort(arr, low = 0, high = arr.length - 1) {
      if (low < high) {
        // 找到基准位置  
        const pivotIndex = partition(arr, low, high);
        // 递归排序左子数组  
        quickSort(arr, low, pivotIndex - 1);
        // 递归排序右子数组  
        quickSort(arr, pivotIndex + 1, high);
      }
      return arr;
    }

    function partition(arr, low, high) {
      // 选择最后一个元素作为基准值  
      const pivot = arr[high];
      let i = low; // 将i初始化为low

      // 遍历数组，重新排列元素  
      for (let j = low; j < high; j++) {
        if (arr[j] < pivot) { //why
          // 交换元素  
          [arr[i], arr[j]] = [arr[j], arr[i]];
          i++;
        }
      }

      // 将基准值放到正确的位置  
      [arr[i], arr[high]] = [arr[high], arr[i]];

      return i; // 返回基准值的索引  
    }
    let arr = [1, 5, 6, 2, 1, 7, 9, 2]
    console.log(quickSort(arr)); //[1, 2, 2, 3, 4, 5, 6]
    console.log(quickSort([3, 8, 6, 4])); //[3,4,6,8]   //这种情况时，left会为空，所以递归结束的条件要包含数组长度为0
  </script>

  <script>

  </script>
</body>

</html>